Day-29 Massive Storage Management

13th鐵人賽

2546 瀏覽

Massive Storage Management

其實這塊要講的就是有關Disk的內容，前面說明Disk的時候就有提到他的構造以及Disk Access Time，也有一張專門說明各種RAID的差別，如果不記得的話底下有幾隻圖片可以複習。

Hard Disk構造	Disk Access Time	RAID

這篇第一件事情要講的事情是OS如何管理空閒的空間，主要有兩種方式，其中一種又會延伸出另外兩種做法，以下一一解釋：

Uploading file..._04mfils1w

我們用一堆Bit來表示每個Block是否空閒，1代表正在被占用，0代表目前空閒。

這種做法簡單又很好尋找連續的Free Space，但是不適合用在大型的Disk，如果Block數量太多，管理的空間就要很大，甚至只能放在Disk中無法放在Memory，效率會大幅下降。

這是一種熟悉的資料結構，每個node會記錄下一個Free Space的位置。

這樣子的做法就適合用在大型的Disk，因為只會使用空閒的Block數量，實施方式也不麻煩，不過不太適合用在尋找連續的Free Space，也不太好尋找大量的Free Space。

基於以上的缺點，Link List的做法有兩種延伸做法，分別為Grouping以及Counting。

不讓一個node只有一個Free Sapce的位址，而是存放多個Free Space位址，如此一來找尋大量Free Space的速度就增加了。

另一個是著重於找尋連續的Free Block，在紀錄Free Sapce位址時，也順便紀錄後面有多少個Free Space，這樣找尋連續Free Block就比較簡單。

雖然上面的圖說的是檔案的起始位置跟大小，不過概念是一樣的。

由於Process會發出許多Disk的需求，這時候OS就要負責哪個需求先處理，以下用表格簡單說明。

法則	作法	效益
FCFS	First Come First Serve，誰先來誰就先處理。	可能導致讀取頭需要左右來回讀取，Seek Time較長。但簡單實施，並且公平。
SSTF	Short Seek Time First，找距離目前最近的先處理。	Seek Time變少，但不一定最佳，並且可能發生Starvation(一直有讀取頭附近的需求，遠處的輪不到)。
SCAN	讀取頭來回跑到底，經過有需求的位址就回傳資料。	效果不錯，公平且適合用在大量需求的狀況，但走到盡頭有點浪費時間。
C-SCAN	類似SCAN，不過永遠回到開頭往後掃描。
Look	類似SCAN，不過掃到最後一個需求位置就往回折返。	可以省去跑到底的時間。
C-Look	類似Look，不過掃到最後一個需求位置之後，直接跳到開頭繼續掃描。